#include<stdio.h>
//归并排序递归实现
void merge(int* a, int* s, int left, int mid, int right) {
    int x = left;
    int b = left;
    int c = mid;
    while ((b < mid) && (c <= right)) {
        if (a[b] >= a[c]) {
            s[x] = a[c];
            c++;
        }
        else {
            s[x] = a[b];
            b++;
        }
        x++;
    }
    while (b < mid) {
        s[x++] = a[b++];
    }
    while (c <= right) {
        s[x++] = a[c++];
    }
}
void MergeSort(int* a, int* s, int left, int right) {
    int t[100];
    if (right == left) {
        s[left] = a[right];
    }
    else {
        int mid = (left + right) / 2;
        MergeSort(a, t, left, mid);
        MergeSort(a, t, mid + 1, right);
        merge(t, s, left, mid+1, right);
    }
}
int main() {
     int array[] = { 1,3,5,7,9,2,4,6,8,0};
     int n = sizeof(array) / sizeof(array[0]);
     MergeSort(array, array, 0, n-1);
     //MergeSortNonR(array, n );
     int i = 0;
     for (i = 0; i < n; i++) {
           printf("%d ", array[i]);
     }
     printf("\n");
     return 0;

}

